Ad hoc networks (i.e., multi-hop packet radio networks) are computer networks in which routers are connected with wireless links. In ad hoc networks, nodes (stations or packet radios) can be mobile and communicate with one another either directly or through intermediate nodes, without relying on any pre-existing network infrastructure.
Many medium-access control (MAC) protocols have been developed for wireless networks. These protocols can be classified as contention-based and schedule-based protocols.
In a contention-based protocol, a node contends for access to the channel on a packet-by-packet basis. This is accomplished by either sending data packets to the channel or by means of a collision-avoidance handshake using small control packets. Examples of the former type of protocols are ALOHA, CSMA, BTMA, CSMA/CD. Examples of collision-avoidance protocols proposed to date include those disclosed in U.S. Pat. Nos. 5,319,64, 4,661,902, 5,231,634, 5,502,724, and 5,721,725. Additional examples include, IEEE802.11, floor acquisition multiple access with non-persistent carrier sensing (FAMA-NCS), receiver intitiated multiple access (RIMA), and multiple access collision avoidance (MACA).
Two key performance limitations of all contention-based protocols, including all collision-avoidance MAC protocols over single or multiple channels are that: (a) they cannot provide channel-access delay guarantees, and (b) they lack explicit support of collision-free multicasting or broadcasting.
To provide delay guarantees and collision-free broadcasting and multicasting, network nodes can use a known transmission schedule or establish such a schedule dynamically to transmit data packets without collisions. Transmission schedules are-established for time periods that are much longer than the duration of a single data packet or just a few data packets. In a transmission schedule, nodes are allowed to transmit at different times and on different data channels (e.g., frequencies, spreading codes, or their combination) in a way that no collisions occur.
The limitations of fixed transmission scheduling are the inability to adapt to network changes and inefficient use of the channel if nodes are bursty sources of traffic.
There are many approaches in the prior art based on dynamic transmission scheduling methods in which stations use ALOHA, slotted ALOHA or other contention-based protocols in an uplink to request time slots from a base station. An example of this approach is the system disclosed in U.S. Pat. No. 5,638,371. A number of protocols have been proposed in the recent past to provide dynamic time-slot allocation without requiring central base stations. These protocols can be classified as topology-independent and topology-dependent time scheduling protocols.
Shepard, “A Channel Access Scheme for Large Dense Packet Radio Networks,” SIGCOMM '96 Conference Proc., ACM 1996, “Scalable, Self-Configuring Packet Radio Network Having Decentralized Channel Management Providing Collision-Free Packet Transfer,” U.S. Pat. No. 5,682,382, Oct. 28, 1997; Chlamtac et al., Chlamtac, W. R. Franta, and K. D. Levin,“BRAM: The Broadcast Recognizing Access Method,” IEEE Trans. Commun., vol. COM-27, pp. 1183-89, 1979, “Fair Algorithms for Maximal Link Activation in Multihop Radio Networks,” IEEE Transactions on Communications, Vol. COM-35, no. 7, July, 1987, “Time-Spread Multiple-Access (TSMA) Protocols for Multihop Mobile Radio Networks,” IEEE/ACM Transactions on Networking, Vol. 5, no. 6, December, 1997; and Ju and Li, Ji-Her Ju, Victor O.K. Li, “An Optimal Topology-Transparent Scheduling Method in Multihop Packet Radio Networks,” IEEE/ACM Transactions on Networking, Vol. 6, no. 3, June 1998, have proposed topology-independent time-scheduling protocols. The protocols proposed by Ephremides and Truong, A. Ephremides, T. Truong, “Scheduling Broadcasts in Multihop Radio Networks,” IEEE Transactions on Communications, Vol. COM-38, No. 4, April, 1990; Corson, C. Zhu, M. S. Corson, “A Five-Phase Reservation Protocol (FPRP) for Mobile Ad Hoc Networks,” Proc. IEEE INFOCOM '98; Young, C. D. Young, “USAP: A Unifying Dynamic Distributed Multichannel TDMA Slot Assignment Protocol,” [apple87] U.S. Pat. No. 4,661,902, April 1987; and Tang and Garcia-Luna-Aceves, Z. Tang and J. J. Garcia-Luna-Aceves, “Hop-Reservation Multiple Access (HRMA) for Multichannel Packet Radio Networks”, Proc. IEEE IC3N '98: Seventh International Conference on Computer Communications and Networks, Lafayette, La., Oct. 12-15, 1998 are examples of topology-dependent scheduling protocols, such that a node acquires a transmission schedule that allows the node to transmit without interfering with nodes one and two hops away from itself, and such that channel reuse is increased as the number of neighbors per node decreases. Robust Environmentally Aware Link and MAC) (REALM) is another example of topology-dependent transmission scheduling; in this protocol, control packets used to exchange transmission schedules are transmitted.
A common feature of all the schedule-based protocols in the prior art consists of assuming that each node has a single radio interface to the wireless network, or that the radios used by a single node (e.g., a base station) operate in orthogonal channels, such as a downlink and an uplink channel in the case of a base station. In practice, however, multiple radio interfaces may be required at a single node to connect to the appropriate nodes in its neighborhood by means of multiple radio transceivers and directional antennas. In addition, two or more nodes with a single transceiver may be located near one another and be connected through a wired interface or a wired LAN. We refer to all these cases as collocated nodes. Collocated nodes present a new problem for the establishment and maintenance of transmission schedules dynamically, because the schedules that they receive from other nodes over wireless channels may be in conflict with one another, simply because different nodes may have radio connectivity with different collocated nodes.